public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] nums1 = new int[]{2,5,1,2,5};
        int[] nums2 = new int[]{10,5,2,1,5,2};
        System.out.println(test.maxUncrossedLines(nums1, nums2));
    }

    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        /**
         * 不相交的线（本质上就是求两个数组之间最长公共子序列的长度）
         * 状态表示：
         *  dp[i][j]表示nums1数组[0,i]范围 与 nums2数组[0,j]范围 这两个范围中最长公共子子序列的长度
         * 状态转移方程：
         *  if(nums1[i] == nums2[j]) {
         *      dp[i][j] = dp[i-1][j-1] + 1;
         *  } else {
         *      dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
         *  }
         * 初始化：
         *  由状态转移方程可得，在填表第一行、第一列时会需要使用到i-1 和 j-1位置的值，会发生数组越界访问
         *  因此我们需要手动赋值
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  return dp[m][n];
         * */
        // 1 预处理
        int m = nums1.length;
        int n = nums2.length;
        // 2 创建dp表
        int[][] dp = new int[m][n];
        // 3 初始化
        for(int k = 0; k < m; k++) {
            if(Solution.isContains(nums1, k, nums2[0])) {
                dp[k][0] = 1;
            }
        }
        for(int k = 0; k < n; k++) {
            if(Solution.isContains(nums2, k, nums1[0])) {
                dp[0][k] = 1;
            }
        }
        // 4 填表
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        // 5 返回值
        return dp[m-1][n-1];
    }

    public static boolean isContains(int[] nums, int end, int target) {
        /**
         * 该方法用于判断一个元素是否存在于数组的某个片段中*/
        for(int i = 0; i <= end; i++) {
            if(target == nums[i]) {
                return true;
            }
        }
        return false;
    }
}
